//
//  main.c
//  110. isBalanced
//
//  Created by edz on 2020/7/13.
//  Copyright © 2020 edz. All rights reserved.
//

/*
 给定一个二叉树，判断它是否是高度平衡的二叉树。
 本题中，一棵高度平衡二叉树定义为：
 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
 示例 1:
 给定二叉树 [3,9,20,null,null,15,7]

     3
    / \
   9  20
     /  \
    15   7
 返回 true 。

 示例 2:
 给定二叉树 [1,2,2,3,3,null,null,4,4]

        1
       / \
      2   2
     / \
    3   3
   / \
  4   4
 返回 false 。
 */

#include <stdio.h>
#include <stdbool.h>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 求最大深度
int maxDepth(struct TreeNode* root){
    if (root == NULL) {
        return 0;
    }
    int countleft = 1 , countright = 1;
    if (root->left) {
        countleft += maxDepth(root->left);
    }
    if (root->right) {
        countright += maxDepth(root->right);
    }
    return countleft > countright ? countleft : countright;
}

bool isBalanced(struct TreeNode* root){
    if (root == NULL) {
        return true;
    }
    int l = maxDepth(root->left);
    int r = maxDepth(root->right);
    if ( l-r > 1 || r-l > 1) {
        return false;
    }
    return isBalanced(root->left) && isBalanced(root->right);
}
